package 力扣_算法题综合.高频面试算法;

import java.util.ArrayDeque;
import java.util.Deque;

public class 字符串解码_394 {
    /**
     * 思路来源
     * https://leetcode.cn/problems/decode-string/solutions/19447/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
     */
    public static String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        int num = 0;
        Deque<Integer> stack_multi = new ArrayDeque<>();// 存储需要重复字符串的数字
        Deque<String> stack_res = new ArrayDeque<>();// 存储待重复的字符串
        for(Character c : s.toCharArray()) {
            if(c == '[') {
                stack_multi.push(num);
                stack_res.push(sb.toString());//把括号前的字母——即将来等待被重复的字符串压栈
                num = 0;// 数字位归0
                sb = new StringBuilder();
            } else if(c == ']') {
                StringBuilder temp = new StringBuilder();
                int cur_multi = stack_multi.pop();//此次要重复的次数数字
                // 本次要重复的完整子串
                for(int i = 0; i < cur_multi; i++){
                    temp.append(sb);
                }
                sb = new StringBuilder(stack_res.pop() + temp);
            } else if(c >= '0' && c <= '9') {
                num = num * 10 + Integer.parseInt(c + "");//数字位题目说明可大于10
            } else if(c >= 'a' && c <= 'z'){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
